1. Field of the Invention
The present invention relates to a motion vector coding method and an affine motion estimation method, and more particularly, to a motion vector coding method capable of producing a low bit rate bitstream and an affine motion estimation method capable of effectively performing coding on a small block.
2. Description of the Related Art
Recently, the International Telecommunication Union-Terminal Sector (ITU-T) has made efforts to standardize the H.26L protocol for next generation visual telephony. Since standard schemes such as H.261, H.263, and H.263+ that define a motion vector coding method for visual telephony were adopted as an ITU-T standard, technologies based on H. 263++ and Moving Picture Experts Group (MPEG)-4 standard schemes have been developed. Nonetheless, there remains a need for further improving coding efficiency for ultra low speed real-time applications and a short end-to-end delay. That is, it is highly desirable to have an estimation method and a motion vector coding method that provide for an improved frame rate at the same bit rate as that of the coding method of the H.263+ standard, or that significantly reduces a bit rate while maintaining the same image quality as that encoded by the H.263+ compliant coding method.
In one conventional motion estimation method, assuming that the pair (i,j) are the coordinates of a macroblock or a sub-block thereof, an affine motion estimation is performed to represent the motion of a pixel in an image using the following Equations (1a) and (1b):
vX(i, j)=a0+a1i+a2jxe2x80x83xe2x80x83(1a)
vY(i, j)=a3+a4i+a5jxe2x80x83xe2x80x83(1b)
where vX(i,j) and vY(i,j) are motion magnitude components of the X- and Y-axis directions for a pixel located in the block (i,j). The expression (vX(i,j), vY(i,j))T, consisting of motion magnitude components vX(i,j) and vY(i,j), is referred to as the motion vector of the pixel located at the coordinates (i,j). That is, the motion vector of each pixel is determined by each pixel location and six parameters (a0, a1, a2, . . . , a5)T. These parameters (a0, a1, a2, . . . , a5)T may be called affine motion parameters. However, according to a method of estimating motion using the affine motion parameters, as the number of bits representing the affine motion parameters increases, computation for a motion estimation becomes more complex and takes more time. Furthermore, with respect to some blocks, this affine motion estimation cannot be more effective than conventional translational motion estimation.
Meanwhile, standards such as H.261, H.263, MPEG-1, and MPEG-2 represent the motion of a pixel based on a translational motion model expressed by:
vX(i,j)=t1xe2x80x83xe2x80x83(2a)
vY(i,j)=t2xe2x80x83xe2x80x83(2b)
As is evident from Equations (2a) and (2b), the motion vectors of all pixels in a block are fixed as one vector. However, in the case of affine motion, as expressed in Equations (1a) and (1b),a motion vector with respect to each pixel location is variable. The affine motion estimation is capable of representing complex motions that include any or all of translations such as rotation, magnification, reduction and shear, thereby allowing for more precise motion estimation.
To estimate the motion of an image using the affine motion estimation, the affine motion parameters as expressed in Equations (1a) and (1b) must be obtained on a block-by-block basis. The motion parameters correspond to displacements that minimize the difference between pixel values for a present image and a preceding motion-compensated image and are expressed by the following Equation (3):                                           arg            ⁢                          xe2x80x83                        ⁢            min                                a            k                          ⁢                              ∑                                          (                                  i                  ,                  j                                )                            ⁢                              εM                k                                              ⁢                      {                                                            I                  n                                ⁡                                  (                                      i                    ,                    j                                    )                                            -                                                                                          I                                              n                        -                        1                                                              (                                          i                      +                                                                        v                          X                                                ⁡                                                  (                                                      i                            ,                            j                                                    )                                                                    +                                                                        v                          Y                                                ⁡                                                  (                                                      i                            ,                            j                                                    )                                                                                                      }                                2                                                                        (        3        )            
where In(i,j) denotes the luminance of the pixel at location (i,j), and Mk denotes the kth block. (vX(i,j), vY(i,j))T is expressed by Equations (1a) and (1b). That is, motion parameters that minimize the luminance difference between a present block and a previous block motion-compensated by the motion parameters are expressed in Equation (3), and the motion parameters are called motion-estimated parameters.
In the affine motion estimation method according to the conventional art, the motion parameters are obtained using the following Equation (4):
akl+1=akl+uklxe2x80x83xe2x80x83(4)
where the term akl=(a0, a1, a2, a3, a4, a5)T, and l denotes an iteration coefficient.
When l equals 0, the motion parameter is expressed by:
ak0=(0,0,0,0,0,0)T
In this case, the motion parameter is called an initial value.       u    k    1    =                    {                              ∑                                          (                                  i                  ,                  j                                )                            ⁢              ε              ⁢                              xe2x80x83                            ⁢              Mk                                ⁢                      {                                          (                                                      h                    ij                    1                                    ⁢                                      (                                          h                      ij                      1                                        )                                                  )                            T                        }                          }                    -        1              ⁢          {              ∑                  {                                                    (                                                      d                    n                    1                                    ⁢                                      (                                          i                      ,                      j                                        )                                                  )                            T                        ⁢                          h              ij              1                                }                    }      xe2x80x83hkl=(Gxl(i,j),iGxl(i,j),jGxl(i,j),Gyl(i,j),jGyl(i,j)T
xe2x80x83dnl(i,j)=In(i,j)xe2x88x92Inxe2x88x921(i,j)(i+a0l+a1li+a2li,j+a3l+a4li+a5lj)xe2x80x83xe2x80x83(8)
GXl(i,j)={In(i+1,j)xe2x88x92Inxe2x88x921(i,j)(i+a0l+a1li+a2ljxe2x88x921,j+a3l+a4li+a5lj}/2xe2x80x83xe2x80x83(9a)
GYl(i,j)={In(i,j+1)xe2x88x92Inxe2x88x921(i,j)(i+a0l+a1li+a2ljxe2x88x921,j+a3l+a4l+a5ljxe2x88x921}/2xe2x80x83xe2x80x83(9b)
The method of estimating the affine motion parameters shown in Equations 4 through 9a and 9b is called a differential motion estimation method. The differential motion estimation method is mostly used in affine motion estimation.
In this case, for affine motion estimation, first, the iteration coefficient 1 is set to xe2x80x9c0xe2x80x9d and the square error is set at a maximum as possible. Next, the value obtained from Equation (6) is updated using Equations 6 through 9a and 9b, and then the updated value is substituted into Equation (4) to thereby obtain akl+1. Then, the difference between the present block and the motion-compensated previous block is obtained using the value akl+1 and the following Equation:                                           SE            ⁡                          (                              1                +                1                            )                                =                                    ∑                              i                ,                                  j                  =                  Mk                                                      ⁢                          {                                                                    I                    n                                    ⁡                                      (                                          i                      ,                      j                                        )                                                  -                                                      I                                          n                      -                      1                                                        (                                                            i                      +                                              a                        0                                                  1                          +                          1                                                                    +                                                                        a                          1                                                      1                            +                            1                                                                          ⁢                        i                                            +                                                                        a                          2                                                      1                            +                            1                                                                          ⁢                        j                                                              ,                                          j                      +                                              a                        3                                                  1                          +                          1                                                                    +                                                                        a                          4                                                      1                            +                            1                                                                          ⁢                        i                                            +                                                                        a                          5                                                      1                            +                            1                                                                          ⁢                        j                                                                                                                                }                            (        10        )            
If SE(l+1) is less than SE(l), l increases by 1 and the above steps are repeatedly performed. If SE(l+1) is greater than SE(l), akl at that time is determined as an estimated motion parameter, and then repetitions of the motion estimation process are terminated.
However, the affine motion estimation method has a problem in that motion estimation performance for small-sized blocks is significantly degraded. Thus, although the affine motion estimation method exhibits an excellent image prediction over the translational motion estimation method, it cannot be applied to standards such as H.261, H.263, MPEG-1, and MPEG-4.
Meanwhile, the affine motion parameters are real numbers with decimal points. Thus, to use these parameters in actual video coding, they must be converted or quantized to fixed-point numbers.
In standards such as H.261, H.263, MPEG-1, and MPEG-4, to which a translational motion model is applied, motion information to be encoded in each block is predictively encoded using motion vectors, thereby reducing the number of bits generated per unit time in a bitstream during coding of the motion information. However, if an affine motion model is used, since each of the six motion parameters shown in Equations (1a) and (1b) is not affected by neighboring blocks, it is very difficult to predictively encode motion information as employed in the translational motion model. That is, a significantly large number of bits may be required in coding a motion parameter of an affine motion model. Thus, it is highly desirable to have a method of effectively coding affine motion parameters.
To solve the above problems, it is an objective of the present invention to provide a method of coding a motion vector that reduces a generated bit rate while maintaining motion estimation performance available from an affine motion estimation.
It is another objective of the present invention to provide a method of estimating motion that is capable of effectively performing coding on a small block.
It is still another objective of the present invention to provide a motion vector decoding method for decoding a bitstream encoded by the motion vector coding method.
Accordingly, to achieve the above objectives, the present invention provides a method of coding a motion vector including the steps of (a) performing an affine motion estimation to obtain affine motion parameters, (b) converting the affine motion parameters to a predetermined number of translational motion vectors, and (c) coding the difference between the converted translational motion vectors of a current block and the converted translational motion vectors of a previous block.
The motion vector coding method further includes the step of quantizing the translational motion vectors in the step (b) to fixed-point numbers having a predetermined accuracy prior to the step (c). Furthermore, the motion vector coding method further includes the step of determining a predetermined pixel range for each translational motion vector of the current block and obtaining an accuracy "PHgr" for each pixel value in the predetermined range, the accuracy "PHgr" producing the smallest value in       min    φϵΠ    ⁢      {                  MSE        ⁢                  (          ϕ          )                    +              λ        ⁢                  xe2x80x83                ⁢                  Bits          ⁢                      (            ϕ            )                                }  
among a set Π of accuracies, where QP is a quantization interval used in coding an image, xcex is a constant determined based on the quantization interval QP, MSE("PHgr") denotes the mean square sum of a differential signal between the current block and the preceding motion-compensated block when translational motion vectors of the current block are represented with an accuracy "PHgr", and Bits ("PHgr") denotes the number of bits used to code the translational motion vector of the current block with an accuracy "PHgr", prior to the step (c).
The method further includes the step of predicting the converted translational motion vectors of the current block by translational motion vectors of neighboring blocks using {circumflex over (V)}x,Ca=median{VX,Cb, VX,Uc, VX,Ud}, {circumflex over (V)}Y,Ca=median{VY,Cb, VY,Uc, VY,Ud}, {circumflex over (V)}X,Cb=median{VX,Ca, VX,Ud, VX,Dc} {circumflex over (V)}Y,Cb=median{VY,Ca, VY,Ud, VY,Dc}, {circumflex over (V)}X,Cc=median{VX,Ld, VX,Ca, VX,Cb}, and {circumflex over (V)}Y,Cc=median{VY,Ld, VY,Ca, VY,Cb}, where a hat denotes an operation for obtaining a predicted value and median { } denotes an operation of obtaining the translational motion vector having the median magnitude among the translational motion vectors.
Step (c) includes the steps of: (c-1) calculating the differences between the translational motion vectors of the current block and the blocks neighboring the current block by using the converted translational motion vectors of the current block and the translational motion vectors of the neighboring blocks; and (c-2) performing variable length coding on the obtained differences between the translational motion vectors.
Step (a) includes the step of obtaining six affine motion estimation parameters (a0, a1, a2, . . . , a5)T by estimating the motion of a pixel in an image using pixel values of a block to be encoded in a current frame and pixel values in a preceding frame and using, vx(i,j)=a0+a1i+a2j, and vY(i,j)=a3+a4i+a5j, where the pair (i,j) are the coordinates of a macroblock or a sub-block thereof.
Step (b) includes the step of obtaining motion vectors of the center points of the sub-blocks A, B, C, and D by using (vx,A,vY,A)=(a0+a1xcex1+a2xcex1,a3+a4xcex1+a5xcex1), (vx,B,vY,B)=(a0+3a1xcex1+a2xcex1,a3+3a4xcex1a5xcex1), and (vx,C,vY,C)=(a0+a1xcex1+3a2xcex1,a3+a4xcex1+3a5xcex1) based on                                           v            X                    ⁡                      (                          i              ,              j                        )                          =                ⁢                                            1                              2                ⁢                α                                      ⁢                          (                                                4                  ⁢                  α                                -                i                -                j                            )                        ⁢                          v                              X                ,                A                                              +                                                ⁢                                            1                              2                ⁢                                  xe2x80x83                                ⁢                α                                      ⁢                          (                                                                    -                    2                                    ⁢                  α                                +                i                            )                        ⁢                          v                              X                ,                B                                      ⁢                          1                              2                ⁢                α                                      ⁢                          (                                                                    -                    2                                    ⁢                  α                                +                j                            )                        ⁢                          v                              X                ,                C                                              ,                                                              v            Y                    ⁡                      (                          i              ,              j                        )                          =                ⁢                                            1                              2                ⁢                                  xe2x80x83                                ⁢                α                                      ⁢                          (                                                4                  ⁢                                      xe2x80x83                                    ⁢                  α                                -                i                -                j                            )                        ⁢                          v                              Y                ,                A                                              +                                    1                              2                ⁢                                  xe2x80x83                                ⁢                α                                      ⁢                          (                                                                    -                    2                                    ⁢                                      xe2x80x83                                    ⁢                  α                                +                i                            )                        ⁢                          v                              Y                ,                B                                              +                                    1                              2                ⁢                                  xe2x80x83                                ⁢                α                                      ⁢                          (                                                                    -                    2                                    ⁢                                      xe2x80x83                                    ⁢                  α                                +                j                            )                        ⁢                                          v                                  Y                  ,                  C                                            .                                          
where one macroblock consists of sub-blocks A, B, C, and D, the size of the macroblock is Sxc3x97S, and the constant xcex1 is S/4+1/2.
After step (b), the motion vector coding method further includes the steps of (bxe2x80x2-1) quantizing the converted translational motion vectors to fixed-point numbers having a predetermined accuracy, (bxe2x80x2-2) selecting an optimum accuracy considering a bit rate and distortion among accuracies, with which the translational motion vectors are represented, and (bxe2x80x2-3) predicting translational motion vectors having the selected accuracy using converted translational motion vectors of neighboring blocks.
Prior to step (a), the method further includes the step of obtaining one translational motion vector for the current block by a block matching technique, and step (a) includes the step (axe2x80x2) performing an affine motion estimation using the obtained translational motion vector as an initial value.
Alternatively, prior to step (a), the method further includes the step of obtaining a motion parameter that minimizes the mean square sum of a difference signal between the current block and the motion-compensated previous block among estimated affine motion parameters of blocks located above the current block and located on the left thereof, and step (a) includes the step of (axe2x80x2) performing an affine motion estimation using the obtained motion parameter as an initial value to obtain affine motion parameters for a predetermined pixel range.
The present invention also provides a method of coding a motion vector including the steps of (a) performing an affine motion estimation to obtain affine motion parameters, (b) obtaining translational motion vectors based on                                           v            X                    ⁡                      (                          i              ,              j                        )                          =                ⁢                                            1                              2                ⁢                α                                      ⁢                          (                                                4                  ⁢                  α                                -                i                -                j                            )                        ⁢                          v                              X                ,                A                                              +                                                ⁢                              1                          2              ⁢                              xe2x80x83                            ⁢              α                                ⁢                      (                                                            -                  2                                ⁢                α                            +              i                        )                    ⁢                      v                          X              ,              B                                ⁢                      1                          2              ⁢              α                                ⁢                      (                                                            -                  2                                ⁢                α                            +              j                        )                    ⁢                      v                          X              ,              C                                ⁢                      xe2x80x83                    ⁢          and                                                              v            Y                    ⁡                      (                          i              ,              j                        )                          =                ⁢                                            1                              2                ⁢                                  xe2x80x83                                ⁢                α                                      ⁢                          (                                                4                  ⁢                                      xe2x80x83                                    ⁢                  α                                -                i                -                j                            )                        ⁢                          v                              Y                ,                A                                              +                                    1                              2                ⁢                                  xe2x80x83                                ⁢                α                                      ⁢                          (                                                                    -                    2                                    ⁢                                      xe2x80x83                                    ⁢                  α                                +                i                            )                        ⁢                          v                              Y                ,                B                                              +                                    1                              2                ⁢                                  xe2x80x83                                ⁢                α                                      ⁢                          (                                                                    -                    2                                    ⁢                                      xe2x80x83                                    ⁢                  α                                +                j                            )                        ⁢                                          v                                  Y                  ,                  C                                            .                                          
size of a block is Sxc3x97S, and the constant xcex1 is S/4+1/2, and (c) coding the difference between the translational motion vectors obtained in step (b).
The present invention also provides a method of coding a motion vector including the steps of: (a) determining a predetermined pixel range for each translational motion vector of a current block; (b) determining the translational motion vector of a current block for each pixel value in the predetermined range, wherein the pixel motion vector is represented with an accuracy "PHgr" that produces the smallest value in       min    ϕεΠ    ⁢      {                  MSE        ⁢                  (          ϕ          )                    +              λ        ⁢                  xe2x80x83                ⁢                  Bits          ⁢                      (            ϕ            )                                }  
among a set Π of accuracies, where QP is a quantization interval used in coding an image, xcex is a constant determined based on the quantization interval QP, MSE("PHgr") denotes the mean square sum of a differential signal between the current block and the preceding motion-compensated block when translational motion vectors of the current block are represented with an accuracy "PHgr", and Bits ("PHgr") denotes the number of bits used to code the translational motion vector of the current block with an accuracy "PHgr"; and (c) coding the difference between the translational motion vectors of the current block and the translational motion vectors of the previous block.
The present invention also provides a method of coding a motion vector including the steps of:(a) determining a predetermined pixel range for each of six translational motion vector components {vX,A, vY,A, vX,B, vY,B, vX,C, vY,C}; (b) obtaining the translational motion vector of a current block for each of the pixel values in the predetermined range determined for each of the six translational motion vector components {vX,A, vY,A, vX,B, vY,B, vX,C, vY,C} in step (a), wherein the pixel motion vector is represented with an accuracy "PHgr" that produces the smallest value in       min    ϕεΠ    ⁢      {                  MSE        ⁢                  (          ϕ          )                    +              λ        ⁢                  xe2x80x83                ⁢                  Bits          ⁢                      (            ϕ            )                                }  
among a set Π of accuracies, where QP is a quantization interval used in coding an image, xcex is a constant determined based on the quantization interval QP, MSE("PHgr") denotes the mean square sum of a differential signal between the current block and the preceding motion-compensated block when translational motion vectors of the current block are represented with an accuracy "PHgr", and Bits ("PHgr") denotes the number of bits used to code the translational motion vector of the current block with an accuracy "PHgr"; and (c) coding the difference between the translational motion vectors obtained in step (b).
The present invention also provides a motion estimation method including the steps of (a) performing an affine motion estimation to obtain affine motion parameters, and (b) converting the affine motion parameters to a predetermined number of translational motion vectors.
The present invention also provides a method of decoding a motion vector including the steps of (a) receiving encoded data, (b) decoding the received data to obtain translational motion vectors, (c) converting the obtained translational motion vectors to affine motion parameters, and (d) performing motion compensation using the obtained affine motion parameters.